n=500;
m=500;
S=2485908000;
ores=[|29998,5181|
18432,30044|
31727,25087|
14071,23878|
31538,20279|
2710,11005|
32077,16462|
18437,22734|
6587,2464|
29890,8851|
17684,12161|
1592,26074|
23868,26493|
28564,19779|
17883,16100|
16852,19242|
10510,2695|
4640,10118|
12381,956|
6750,9489|
18924,13992|
18433,426|
19957,9661|
11553,22007|
6261,18049|
2001,6222|
27430,15249|
21421,18134|
11182,28646|
6578,31977|
21014,30552|
29267,30653|
7037,22624|
28104,20036|
21774,8994|
22186,24656|
21295,31147|
701,16635|
26875,28023|
9741,8262|
29683,22070|
23612,30720|
20464,1487|
23578,32746|
18269,32166|
2422,11544|
21410,2331|
22836,16538|
16867,24915|
15264,10588|
4075,15930|
258,15691|
5475,30920|
27763,3513|
19784,8836|
26862,23299|
21404,13895|
5290,27505|
27483,17987|
5799,18781|
8368,19267|
29319,11416|
23401,31028|
20128,4873|
30121,15589|
24655,19607|
10972,18187|
29327,32330|
29424,18568|
15050,24748|
7619,17389|
28655,15734|
17111,6205|
22468,28776|
22861,10484|
15998,28537|
3089,18247|
3215,7728|
7762,16558|
28351,28754|
29749,13984|
17534,8125|
5066,9117|
18552,31124|
12863,12658|
10091,1692|
8531,17593|
31029,4838|
12558,24991|
20530,22703|
22959,19946|
21188,21124|
16871,5178|
4915,30890|
30020,19598|
6584,28092|
24304,19979|
21716,24214|
23707,11769|
25574,6514|
32182,12303|
28669,8273|
17122,3056|
1771,15005|
29096,11253|
11419,18956|
20586,18733|
5796,26311|
24217,2210|
17949,1740|
23849,32222|
29620,13456|
15170,13998|
506,6377|
15161,13350|
27137,23596|
25534,29925|
22057,8850|
4439,29851|
24375,10209|
15373,17608|
8103,15944|
17764,8902|
4420,13450|
25233,12041|
26869,26463|
30440,10662|
25818,535|
29332,22546|
16535,12928|
2442,30764|
17392,21514|
22208,25726|
8087,22057|
16281,19904|
3137,25083|
11172,11678|
24575,811|
25735,22204|
3532,22549|
12854,17910|
17250,3370|
1897,6380|
6483,10134|
21068,19902|
2388,25377|
17784,12308|
7900,10067|
11554,5986|
5614,22492|
9362,23146|
23602,1075|
16343,7170|
10315,14972|
32186,21783|
7013,431|
5616,16370|
8461,16119|
30612,2234|
326,2648|
3028,26426|
22745,13973|
4330,1509|
27628,4177|
8526,23063|
1750,6260|
15145,20894|
24882,15824|
23565,31097|
14130,23045|
1252,479|
3383,30113|
14887,17284|
20894,6028|
21585,10775|
20700,9124|
13458,10255|
12237,3236|
12743,6055|
24649,23882|
20906,11559|
17401,23737|
8774,24166|
29032,21020|
18351,25485|
20317,11148|
4591,13597|
31337,3124|
12099,11060|
10428,1458|
20104,8716|
60,193|
17904,18372|
4825,6421|
4601,30563|
29978,28807|
16544,17690|
8956,15730|
7377,8137|
9981,6237|
11811,11205|
14196,19674|
24770,15065|
15907,12717|
27052,1418|
32271,19505|
15137,2463|
19344,17144|
7508,12769|
2724,25522|
16231,11040|
26504,16464|
21654,2678|
32138,10089|
4531,10448|
24601,31708|
7890,22441|
14878,12215|
20805,21273|
30607,26199|
16843,5391|
11584,465|
4868,28122|
13053,8081|
31784,1519|
9175,18497|
27641,11494|
14523,22253|
22518,6597|
12617,23396|
3026,129|
16098,31713|
3364,8386|
9731,6634|
26464,12775|
2514,15993|
29702,20554|
5623,4442|
29465,20421|
31405,24532|
2003,6005|
28441,30347|
28055,27325|
11738,21157|
31015,17294|
8161,28204|
14871,8678|
10627,11187|
20610,29847|
19916,9533|
19195,32586|
7191,25178|
8390,25027|
7131,14739|
7241,9319|
10952,24840|
18877,28155|
275,29272|
15913,18094|
20494,26049|
19089,3162|
12027,18569|
28522,31751|
18978,12956|
9298,29873|
2081,16246|
18430,22347|
6532,3651|
19572,10243|
9877,3397|
29562,21704|
3957,5239|
12110,17673|
29292,4976|
31639,5824|
27774,22153|
17052,11440|
18495,10050|
8884,29162|
3816,19426|
10237,30358|
12201,10846|
20049,18928|
12609,4732|
24438,13713|
8653,29496|
405,15856|
14557,32615|
2542,3112|
24525,1434|
26569,9468|
5203,32581|
15280,4376|
22868,6945|
28379,23193|
10748,18126|
24300,976|
8973,31677|
29149,23363|
22135,21325|
9782,20725|
32042,9780|
29571,12520|
31528,15137|
3845,26335|
27102,18592|
26792,12136|
7348,20029|
29749,23066|
21475,2284|
4809,284|
4486,1704|
12422,23015|
17653,7515|
27272,844|
16462,18686|
20762,29880|
11348,13569|
6698,29367|
28285,29933|
22523,11447|
13638,12360|
2074,26639|
7882,17849|
3731,23615|
11667,10604|
29028,9337|
32688,696|
26674,27233|
31751,19711|
5179,11794|
27117,32726|
29836,20321|
9972,614|
27252,15461|
28420,28178|
25144,26935|
27310,25691|
29704,29942|
30652,31744|
4402,8206|
24589,2409|
4502,30650|
29344,17989|
13658,23240|
13038,7283|
28383,15261|
4733,6174|
2291,17272|
26802,17709|
32072,15099|
7399,31706|
3876,23527|
14013,24736|
32347,28711|
18611,7003|
26235,25104|
26872,2475|
7750,8679|
11390,28825|
11109,1187|
22608,29053|
7770,32757|
15653,17951|
27319,26502|
28981,2076|
3981,3968|
23627,1931|
9256,30799|
18972,29921|
7417,26537|
30423,25106|
23764,4811|
18941,24313|
26204,15878|
13171,13562|
16827,30075|
24278,1510|
27286,17187|
12558,21022|
23103,1554|
17446,10748|
557,20220|
21850,3694|
19114,26104|
22898,17636|
27084,23940|
11087,8813|
9894,22217|
2244,4636|
23743,23329|
20903,23217|
21444,28375|
15655,26485|
16249,16686|
31071,6246|
31733,7588|
26924,23956|
23055,631|
29756,8651|
4116,105|
7528,18546|
8891,18368|
21316,17075|
23130,1682|
12020,32733|
6233,31807|
5441,15622|
8423,26175|
28140,30708|
11501,10782|
25921,2366|
22592,24772|
27632,10670|
16411,9978|
26905,26346|
26060,22314|
21158,19283|
10669,4198|
8157,15662|
29270,11948|
18997,22786|
21521,6249|
20585,19264|
19599,1339|
28620,27945|
26329,8699|
2012,10477|
23432,13819|
23577,26896|
313,11660|
10264,5906|
8508,11716|
14803,27983|
1164,5502|
1603,8228|
19716,4001|
27697,8787|
28367,6822|
6473,2217|
24097,10580|
17776,20702|
17700,16590|
14423,4028|
22070,14288|
19792,19075|
3665,31542|
26977,32653|
31690,31678|
6039,8750|
23871,10510|
16285,3550|
11467,7673|
10893,13466|
27515,25086|
18950,3207|
16646,25617|
30079,217|
17336,4767|
4571,27123|
31920,13516|
22333,20687|
31819,26879|
10525,417|
4832,27808|
13468,12727|
430,4384|
18708,15524|
14354,570|
7924,15517|
28926,16761|
203,547|
17574,31483|
2722,12003|
636,6004|
29583,30682|
26463,12149|
5511,21180|
1039,17391|
10100,4759|
26597,24563|
23943,14259|
25537,1979|
25552,30398|
31043,6382|
26380,15141|
19006,32|
8126,10437|
7273,26520|
4993,24771|
17752,17239|
156,3512|
4779,24150|
10199,31506|
646,19726|
26765,15287|
24641,26941|
25347,9195|
6496,15080|
5368,6771|];
intervals=[|261,340|
274,341|
148,278|
219,429|
4,387|
239,399|
248,335|
79,233|
252,317|
84,256|
193,370|
228,457|
255,489|
82,384|
130,167|
153,168|
104,453|
124,484|
3,424|
194,391|
53,281|
240,357|
316,404|
95,161|
41,283|
107,335|
295,356|
55,468|
60,65|
112,149|
269,286|
6,197|
76,500|
99,169|
391,408|
25,190|
382,484|
74,118|
21,439|
195,394|
59,376|
272,343|
305,464|
80,205|
26,92|
81,354|
65,377|
50,204|
109,441|
110,119|
51,424|
335,339|
15,441|
14,446|
119,273|
29,165|
161,283|
204,481|
293,327|
156,296|
158,260|
88,239|
15,376|
343,394|
287,496|
75,279|
107,126|
153,203|
46,320|
37,399|
125,165|
282,432|
149,233|
74,473|
337,484|
118,449|
125,350|
9,456|
42,436|
133,276|
226,462|
116,412|
210,318|
17,366|
205,453|
159,322|
185,347|
4,17|
15,366|
285,298|
44,50|
406,491|
88,485|
446,496|
423,498|
152,168|
134,454|
123,242|
144,245|
194,245|
350,497|
410,470|
82,368|
13,333|
35,387|
460,476|
55,327|
140,369|
121,222|
178,431|
191,432|
56,496|
65,155|
119,224|
6,53|
285,413|
338,446|
133,154|
85,354|
42,271|
93,332|
25,292|
170,257|
31,158|
101,296|
10,32|
2,319|
16,89|
218,441|
109,220|
206,416|
115,483|
353,378|
28,280|
91,295|
196,211|
10,450|
42,77|
102,355|
251,270|
13,406|
73,113|
142,259|
212,402|
429,465|
360,425|
102,277|
156,483|
375,455|
50,492|
335,375|
83,260|
237,429|
90,483|
22,214|
16,370|
368,403|
148,488|
37,121|
79,324|
142,450|
245,422|
97,300|
275,465|
112,288|
208,252|
52,265|
42,280|
49,119|
267,361|
142,334|
63,288|
42,421|
363,458|
128,405|
75,286|
307,454|
15,213|
315,449|
165,257|
98,272|
42,137|
183,461|
252,361|
82,115|
233,300|
13,289|
133,415|
9,65|
401,491|
105,236|
397,434|
111,442|
201,242|
100,237|
74,121|
339,472|
2,116|
395,490|
9,470|
325,500|
101,161|
116,331|
184,186|
17,152|
26,38|
62,249|
85,404|
161,372|
269,279|
149,306|
1,100|
106,333|
202,320|
96,206|
166,500|
103,201|
79,270|
90,426|
7,230|
63,88|
325,456|
113,128|
272,464|
182,226|
166,178|
172,395|
142,493|
148,466|
246,314|
395,411|
300,464|
44,255|
191,362|
27,271|
141,187|
370,429|
78,428|
20,165|
105,395|
52,211|
51,303|
71,462|
81,313|
14,327|
28,242|
56,159|
209,368|
421,429|
30,438|
266,423|
137,409|
154,190|
30,209|
148,314|
262,437|
115,211|
421,441|
257,294|
443,486|
86,414|
229,341|
320,405|
160,247|
127,476|
17,89|
7,259|
214,416|
134,450|
85,149|
193,220|
271,316|
83,116|
172,313|
220,282|
180,408|
120,225|
332,452|
338,375|
102,247|
118,270|
400,410|
142,303|
145,392|
377,391|
138,368|
21,125|
353,482|
267,400|
223,304|
202,210|
37,408|
158,425|
38,118|
76,318|
42,485|
311,366|
303,382|
108,212|
67,191|
28,455|
127,207|
19,465|
153,331|
45,310|
96,490|
159,483|
14,387|
185,338|
200,295|
105,255|
32,490|
240,272|
277,280|
150,448|
15,255|
40,225|
66,222|
97,297|
128,133|
125,443|
117,407|
39,235|
111,475|
98,489|
34,297|
146,274|
303,479|
315,377|
157,163|
221,439|
394,456|
136,354|
36,360|
21,165|
312,343|
169,313|
129,135|
256,471|
208,410|
240,402|
190,341|
109,112|
173,232|
384,395|
423,471|
75,425|
76,228|
311,404|
41,209|
91,258|
88,432|
18,174|
229,422|
110,224|
80,372|
263,402|
230,415|
57,498|
139,454|
253,335|
191,195|
51,471|
393,496|
2,334|
297,443|
237,238|
141,457|
444,454|
142,218|
180,354|
37,189|
15,492|
258,263|
21,338|
86,416|
25,253|
116,352|
146,322|
63,137|
475,489|
16,156|
197,415|
135,362|
12,396|
70,293|
102,381|
43,137|
54,183|
354,449|
60,116|
283,335|
184,195|
159,450|
40,296|
262,288|
219,295|
89,96|
383,491|
105,175|
44,236|
94,192|
151,222|
114,129|
2,187|
29,367|
114,421|
53,66|
132,203|
15,217|
18,140|
92,461|
190,431|
232,449|
65,492|
192,347|
22,89|
52,334|
51,63|
69,104|
204,250|
420,472|
71,196|
139,374|
21,445|
401,424|
382,459|
241,302|
109,378|
228,359|
37,65|
15,148|
136,311|
164,217|
58,161|
61,128|
104,353|
67,183|
185,431|
395,404|
170,335|
9,93|
246,335|
36,387|
69,463|
263,294|
27,297|
263,500|
122,315|
65,413|
9,377|
209,323|
77,159|
157,264|
12,459|
29,440|
390,401|
122,214|
332,438|
92,455|
329,419|
17,19|
181,234|
144,335|
128,251|
112,373|
67,315|
161,352|
140,438|
334,446|
18,113|
118,194|
243,370|
276,484|
97,260|
289,314|
70,239|
187,278|
291,493|
4,476|
110,406|
70,328|
75,385|
226,435|
102,205|
155,214|
47,458|
16,91|
343,488|
34,404|
263,330|
45,226|
50,478|
165,184|
14,92|
12,182|
45,84|
357,386|
162,477|
145,392|];